package com.zlk.algorithm.dataStructure.graph.impl;
import java.util.*;

/**
 * @program: algorithm
 * @ClassName GraphList
 * @description:邻接表法
 * @author: slfang
 * @create: 2024-03-20 11:11
 * @Version 1.0
 **/
public class GraphList {
    /**
     * 顶点的个数
     */
    private int v;
    /**
     * 邻接表
     */
    private LinkedList[] adj;

    public GraphList(int v){
        this.v = v;
        this.adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList();
        }
    }


    public void addEdge(int a,int b){
        adj[a].add(b);
    }


    public int getV() {
        return v;
    }

    public LinkedList[] getAdj() {
        return adj;
    }


    public static void main(String[] args) {
        GraphList graph = new GraphList(7);
        graph.creatEdge();
        //graph.dfs(0,3);
    }

    private void creatEdge() {
        addEdge(0,1);
        addEdge(0,2);
        addEdge(0,6);
        addEdge(0,5);
        addEdge(5,3);
        addEdge(4,3);
        addEdge(4,5);
        addEdge(4,6);
    }


    public ArrayList<Integer> sort(){
        //使用map的目的是不破坏原有结构
        HashMap<Integer,Integer> inDegreeMap = new HashMap<>();
        Queue<Integer> zeroQueue = new LinkedList<>();
        for (int i = 0; i < adj.length; i++) {
            inDegreeMap.put(i,0);
        }
        for (int i = 0; i < adj.length; i++) {
            for (Object next : adj[i]) {
                int index = (int)next;
                if(inDegreeMap.containsKey(index)){
                    inDegreeMap.put(index,inDegreeMap.get(index)+1);
                }else{
                    inDegreeMap.put(index,1);
                }
            }
        }

        for (Map.Entry<Integer, Integer> integerIntegerEntry : inDegreeMap.entrySet()) {
            if(integerIntegerEntry.getValue()==0){
                zeroQueue.add(integerIntegerEntry.getKey());
            }
        }

        ArrayList<Integer> ans = new ArrayList<>();
        while (!zeroQueue.isEmpty()){
            Integer cur = zeroQueue.poll();
            ans.add(cur);
            for (Object next : adj[cur]) {
                int index = (int)next;
                Integer integer = inDegreeMap.get(index);
                int newIn = integer-1;
                inDegreeMap.put(index,newIn);
                if(newIn==0){
                    zeroQueue.add(index);
                }
            }
        }
        return ans;
    }
}
